package code.D1218;

/**
 * author : yeswater
 * date : 2023/12/18
 *
 * 完全平方数
 *
 */

public class T279 {
    /**
     * 首先初始化长度为 n+1 的数组 dp[n+1] 每个位置都为 0
     * 如果 n = 0， 则结果为 0
     * 对数组进行遍历 下标为 i 每次都将当前数字先更新为最大的结果
     * 即 dp【i】 = i  比如 i= 4 最坏结果为 4 = 1+1+1+!
     * 动态转移方程 dp[i] = Math.min(dp[i], dp[i-j*j]+1) i 表示当前数字 j*j 表示平方数
     *
     * dp[i] 的含义： i位置完全平方数的最少数量
     * dp[i-j*j]+1 中 +1的含义是： 加上当前 j的平方
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
            }
        }
        return dp[n];
    }
}
